home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_TOOL / TOOLS / TOOLS_WI / BYACC__ / CLOSURE.C < prev    next >
C/C++ Source or Header  |  1989-11-19  |  4KB  |  274 lines
  1. #include <stdio.h>
  2. #include "defs.h"
  3. #include "dep.h"
  4. #include "new.h"
  5. #include "gram.h"
  6.  
  7. short *itemset;
  8. short *itemsetend;
  9. unsigned *ruleset;
  10.  
  11. LOCAL unsigned *first_derives;
  12. LOCAL unsigned *EFF;
  13.  
  14.  
  15. set_EFF()
  16. {
  17.   register unsigned *row;
  18.   register int symbol;
  19.   register short *sp;
  20.   register int rowsize;
  21.   register int i;
  22.   register int rule;
  23.  
  24.   rowsize = WORDSIZE(nvars);
  25.   EFF = NEW2(nvars * rowsize, unsigned);
  26.  
  27.   row = EFF;
  28.   for (i = start_symbol; i < nsyms; i++)
  29.     {
  30.       sp = derives[i];
  31.       for (rule = *sp; rule >= 0; rule = *++sp)
  32.     {
  33.       symbol = ritem[rrhs[rule]];
  34.       if (ISVAR(symbol))
  35.         {
  36.           symbol -= ntokens;
  37.           SETBIT(row, symbol);
  38.         }
  39.     }
  40.       row += rowsize;
  41.     }
  42.  
  43.   reflexive_transitive_closure(EFF, nvars);
  44.  
  45. #ifdef    DEBUG
  46.   print_EFF();
  47. #endif
  48. }
  49.  
  50.  
  51. set_first_derives()
  52. {
  53.   register unsigned *rrow;
  54.   register unsigned *vrow;
  55.   register int j;
  56.   register unsigned mask;
  57.   register unsigned cword;
  58.   register short *rp;
  59.  
  60.   int rule;
  61.   int i;
  62.   int rulesetsize;
  63.   int varsetsize;
  64.  
  65.   rulesetsize = WORDSIZE(nrules);
  66.   varsetsize = WORDSIZE(nvars);
  67.   first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
  68.  
  69.   set_EFF();
  70.  
  71.   rrow = first_derives + ntokens * rulesetsize;
  72.   for (i = start_symbol; i < nsyms; i++)
  73.     {
  74.       vrow = EFF + ((i - ntokens) * varsetsize);
  75.       cword = *vrow++;
  76.       mask = 1;
  77.       for (j = start_symbol; j < nsyms; j++)
  78.     {
  79.       if (cword & mask)
  80.         {
  81.           rp = derives[j];
  82.           while ((rule = *rp++) >= 0)
  83.         {
  84.           SETBIT(rrow, rule);
  85.         }
  86.         }
  87.  
  88.       mask <<= 1;
  89.       if (mask == 0)
  90.         {
  91.           cword = *vrow++;
  92.           mask = 1;
  93.         }
  94.     }
  95.  
  96.       vrow += varsetsize;
  97.       rrow += rulesetsize;
  98.     }
  99.  
  100. #ifdef    DEBUG
  101.   print_first_derives();
  102. #endif
  103.  
  104.   FREE(EFF);
  105. }
  106.  
  107.  
  108. closure(core, n)
  109. short *core;
  110. int n;
  111. {
  112.   register int ruleno;
  113.   register unsigned word;
  114.   register unsigned mask;
  115.   register short *csp;
  116.   register unsigned *dsp;
  117.   register unsigned *rsp;
  118.   register int rulesetsize;
  119.  
  120.   short *csend;
  121.   unsigned *rsend;
  122.   int symbol;
  123.   int itemno;
  124.  
  125.   rulesetsize = WORDSIZE(nrules);
  126.   rsp = ruleset;
  127.   rsend = ruleset + rulesetsize;
  128.   csend = core + n;
  129.  
  130.   while (rsp < rsend)
  131.     *rsp++ = 0;
  132.  
  133.   csp = core;
  134.   while (csp < csend)
  135.     {
  136.       symbol = ritem[*csp++];
  137.       if (ISVAR(symbol))
  138.     {
  139.       dsp = first_derives + symbol * rulesetsize;
  140.       rsp = ruleset;
  141.       while (rsp < rsend)
  142.         *rsp++ |= *dsp++;
  143.     }
  144.     }
  145.  
  146. ruleno = 0;
  147.   itemsetend = itemset;
  148.   csp = core;
  149.   rsp = ruleset;
  150.   while (rsp < rsend)
  151.     {
  152.       word = *rsp++;
  153.       if (word == 0)
  154.     {
  155.       ruleno += BITS_PER_WORD;
  156.     }
  157.       else
  158.     {
  159.       mask = 1;
  160.       while (mask)
  161.         {
  162.           if (word & mask)
  163.         {
  164.           itemno = rrhs[ruleno];
  165.           while (csp < csend && *csp < itemno)
  166.             *itemsetend++ = *csp++;
  167.           *itemsetend++ = itemno;
  168.         }
  169.  
  170.           mask <<= 1;
  171.           ruleno++;
  172.         }
  173.     }
  174.     }
  175.  
  176.   while (csp < csend)
  177.     *itemsetend++ = *csp++;
  178.  
  179. #ifdef    DEBUG
  180.   print_closure(n);
  181. #endif
  182. }
  183.  
  184.  
  185.  
  186. finalize_closure()
  187. {
  188.   FREE(itemset);
  189.   FREE(ruleset);
  190.   FREE2(first_derives,ntokens * WORDSIZE(nrules));
  191. }
  192.  
  193.  
  194. #ifdef    DEBUG
  195.  
  196. print_closure(n)
  197. int n;
  198. {
  199.   register short *isp;
  200.  
  201.   printf("\n\nn = %d\n\n", n);
  202.   for (isp = itemset; isp < itemsetend; isp++)
  203.     printf("   %d\n", *isp);
  204. }
  205.  
  206.  
  207. print_EFF()
  208. {
  209.   register int i;
  210.   register int j;
  211.   register int k;
  212.   register unsigned *rowp;
  213.   register unsigned cword;
  214.   register unsigned mask;
  215.  
  216.   printf("\n\nEpsilon Free Firsts\n");
  217.  
  218.   for (i = start_symbol; i < nsyms; i++)
  219.     {
  220.       printf("\n%s", symbol_name[i]);
  221.       rowp = EFF + ((i - ntokens) * WORDSIZE(nvars));
  222.       cword = *rowp++;
  223.       mask = 1;
  224.       for (j = 0; j < nvars; j++)
  225.     {
  226.       if (cword & mask)
  227.         printf("  %s", symbol_name[start_symbol + j]);
  228.  
  229.       mask <<= 1;
  230.       if (mask == 0)
  231.         {
  232.           cword = *rowp++;
  233.           mask = 1;
  234.         }
  235.     }
  236.     }
  237. }
  238.  
  239.  
  240. print_first_derives()
  241. {
  242.   register int i;
  243.   register int j;
  244.   register unsigned *rp;
  245.   register unsigned cword;
  246.   register unsigned mask;
  247.  
  248.   printf("\n\n\nFirst Derives\n");
  249.  
  250.   for (i = start_symbol; i < nsyms; i++)
  251.     {
  252.       printf("\n%s derives\n", symbol_name[i]);
  253.       rp = first_derives + i * WORDSIZE(nrules);
  254.       cword = *rp++;
  255.       mask = 1;
  256.       for (j = 0; j <= nrules; j++)
  257.         {
  258.       if (cword & mask)
  259.         printf("   %d\n", j);
  260.  
  261.       mask <<= 1;
  262.       if (mask == 0)
  263.         {
  264.           cword = *rp++;
  265.           mask = 1;
  266.         }
  267.     }
  268.     }
  269.  
  270.   fflush(stdout);
  271. }
  272.  
  273. #endif
  274.